package solutions.leetcode.hard

/**
 * @author lizhidong
 * <a href="https://leetcode.cn/problems/count-increasing-quadruplets/">2552. 统计上升四元组</a>
 */
private class Solution2552 {
    /*
    1   3   2   6   7   4   5   8

    1   1   1   1   1   1
    0   1   1   3   4   3
    0   1   0   3   3   0
    0   0   0   1   1   1
     */
    fun countQuadruplets(nums: IntArray): Long {
        var rst: Long = 0
        val canThree = IntArray(nums.size)
        for (i in 1 until nums.size) {
            var c = 0
            for (j in 0 until i) {
                if (nums[j] < nums[i]) {
                    c++
                    rst += canThree[j]
                } else {
                    canThree[j] += c
                }
            }
        }
        return rst
    }
}

fun main() {
    println(Solution2552().countQuadruplets(arrayOf(
        1,3,2,4,5
    ).toIntArray()))
}